package query;


//        二分查找的前提条件是有序数列，普通查找则不需要。
//        查找到返回该元素的下标，否则返回-1。
//        普通查找的时间复杂度为O(N), 二分查找的时间复杂度为O(logN)。
//        2^m=N(m为折半查找的次数)，那么m=log(N)，二分查找的时间复杂度就为O(logN)。
//
public class BinarySearch {

    public static int binarySearch1(int[] list, int key)
    {
        int low = 0;
        int high = list.length - 1;
        while (low <= high)
        {
            int mid = (low + high) / 2;
            if (key < list[mid])
            {
                high = mid - 1;
            }
            else if (key > list[mid])
            {
                low = mid + 1;
            }
            else
            {
                return mid;
            }

        }
        return -1;
    }
}
